package com.zklh.leetcode.dynamic;

/**
 * 下降路径最小和
 *
 * @author tongnan
 * @date 2025/10/9
 */
public class Solution931 {
    public int minFallingPathSum(int[][] matrix) {
        int len = matrix.length;
        for (int x = 1; x < len; x++) {
            for (int y = 0; y < len; y++) {
                int min = matrix[x-1][y];
                if (y - 1 >= 0) {
                    min = Math.min(min, matrix[x-1][y-1]);
                }
                if (y + 1 < len) {
                    min = Math.min(min, matrix[x-1][y+1]);
                }
                matrix[x][y] = matrix[x][y] + min;
            }
        }
        int min = matrix[len-1][0];
        for (int i = 0; i < len; i++) {
            min = Math.min(min, matrix[len-1][i]);
        }
        return min;
    }
}
